1. Field of the Invention
This invention relates generally to methods and apparatus for manipulating graphical image data for presentation on a graphical display. More particularly, this invention relates to methods and apparatus for up-scaling graphical image data intended for presentation on a display with a lower resolution to graphical image data for presentation on a display with a higher resolution. Even more particularly, this invention relates to methods and apparatus for up-scaling graphical image data by interpolation of the horizontal pixel image data followed by interpolation of the vertical pixel image data.
2. Description of Related Art
Conventional devices for presenting a graphics image include such display devices as computer monitors (CRT displays, flat panel LCD displays, or plasma displays), projectors, or other imaging system. These devices produce a displayed image by addressing an array of individual picture elements or pixels arranged in ranks of horizontal rows and vertical columns. The resolution of the displayed image is defined as the number of horizontal rows and vertical columns of individual pixels forming the displayed image. The resolution of the displayed image is determined by the resolution of the display device onto which the image data is intended to be displayed.
The display devices have a preferred operational mode or display mode. The term display mode refers to the characteristics of a display device, in particular the maximum number of colors and the maximum image resolution (in pixels horizontally by pixels vertically). There are several display modes are presently used in display devices. The present most common display modes in use include the Video Graphics Array (VGA), the Extended Graphics Array (XGA), the Super Video Graphics Array (SVGA), the Super Extended Graphics Array (SXGA) and Ultra Extended Graphics Array (UXGA). Table 1 shows display modes and the resolution levels (in pixels horizontally by pixels vertically) most commonly associated with each.
TABLE 1Display ModeResolution (pixels)VGA640 × 480SVGA800 × 600XGA1024 × 768 SXGA1280 × 1024UXGA1600 × 1200
Often, the resolution of the image data and the resolution of the display device differ. In the cases where the image data is stored at a resolution less than the display device, the image will under fill the display device and there will be blank spaces horizontally and vertically from the presented image. In some instances the image maybe stored in a standard 4:3 aspect ratio, but need to be presented on a display device that has a standard 16:9 aspect ratio. Again, this difference in image resolution and aspect ratio causes the image to not fit onto the display device appropriately. To fill the display device the image data must be up-scaled. Conventionally the image data must be interpolated between the pixels of each row of image data to add pixels to the row and then the rows of image pixel data are interpolated to add needed rows of image pixel data.
U.S. Pat. No. 5,739,867 (Eglit) describes an up-scaler for up-scaling a source image to generate a destination image without having to maintain the aspect ratio (ratio of the length of the source image to that of the width) of the source image. The source image pixel data is received at a first clock rate and the destination image is generated at a second clock rate. The second clock rate is computed such that the frame rate at which the source image is received is the same as the frame rate at which the up-scaled image is generated. Because of such a clock rate, the up-scaler may be implemented only a line buffer for up-scaling a source image.
The operation of the up-scaler of Eglit is shown in FIG. 1. The source pixel data 5 is applied to the input data synchronizer 10 using source clock timing signals 7 SCLK and sends the synchronized source pixel data to line buffer 20 synchronized at the rate determined by the source clock timing signals 7 SCLK. However, the rate of data flow is the same at the input and output sides of input data synchronizer 10 and corresponds to the rate of the source clock timing signals 7 SCLK.
The line buffer 20 receives synchronized image pixel data at the same data flow rate as the output rate of input data synchronizer 10 and transfers the synchronized image pixel data to the first-in-first out serial memory (FIFO) 25 at a rate determined by the destination clock timing signals 15 DCLK.
The output is the first-in-first out serial memory 25 is then transferred to the interpolator line buffer 30 and the vertical interpolator 35. The interpolator line buffer 30 retains at least one complete horizontal line grouping of pixel image data for interpolation with an incoming horizontal line grouping of pixel image data. The vertical interpolator 35 performs an appropriate interpolation function to add the necessary lines to the pixel image data for filling the vertical space of the display device. The vertically interpolated data is then transferred from the vertical interpolator to the horizontal interpolator 40. The transfer of the synchronized pixel image data to the vertical interpolator from the first-in-first out serial memory 25 and the interpolator line buffer 30 is at the rate of the destination clocking signals 15. Further, the vertical interpolation operations of the vertical interpolator 35 are performed at the rate of the rate of the destination clocking signals 15.
The horizontal interpolator receives the vertically interpolated pixel image data, the interpolation operation and transfers the interpolated pixel image data as the destination pixel image data 45 at the intermediate speed data flow rate of the destination clocking signals 15 to the display device control circuitry.
“Scattered Data Interpolation Methods for Electronic Imaging Systems: A Survey”, Amidror, Journal of Electronic Imaging, Vol. 11, Issue 2, pp.: 157-176, April 2002, describes methods for scattered data interpolation in two-dimensional and in three-dimensional spaces for electronic imaging systems. The methods described include linear interpolation, bilinear interpolation methods, bicubic interpolation methods, triangulation interpolation methods, tetrahedrization interpolation methods, inverse distance weighted interpolation methods, radial basis function interpolation methods; and natural neighbor interpolation methods.
“Survey: Interpolation Methods in Medical Image Processing”, Lehmann, et al., IEEE Transactions on Medical Imaging, 1999, Volume: 18, Issue: 11, pp: 1049-1075, describes image interpolation techniques that are required in medical imaging for image generation (e.g., discrete back projection for inverse Radon transform) and processing such as compression or resampling. Since the ideal interpolation function spatially is unlimited, several interpolation kernels of finite size have been introduced. Lehman et al. compares 1) truncated and windowed sine; 2) nearest neighbor; 3) linear; 4) quadratic; 5) cubic B-spline; 6) cubic; g) Lagrange; and 7) Gaussian interpolation and approximation techniques with kernel sizes from 1×1 up to 8×8. The comparison is done by: 1) spatial and Fourier analyses; 2) computational complexity as well as runtime evaluations; and 3) qualitative and quantitative interpolation error determinations for particular interpolation tasks which were taken from common situations in medical image processing.
“Arbitrarily Scalable Edge-Preserving Interpolation for 3-D Graphics and Video Resizing”, Lee, The 2001 IEEE International Symposium on Circuits and Systems—ISCAS 2001, Volume: 2, pp.: 317-320, teaches proposes an edge-preserving interpolation algorithm that can perform arbitrary scaling. The algorithm utilizes a band-split approach with weighted selection direction interpolation.
U.S. Pat. No. 4,988,984 (Gonzalez-Lopez) illustrates an image interpolator that implements an interpolation function providing real time, continuous zoom capability to an image display system. Output image pixels are obtained by interpolating the values of the color or intensity of the 2×2 matrix of pixels surrounding the point on the input image. The interpolator employs a bi-linear interpolation algorithm implemented in the form of cascaded one-dimensional interpolation circuits. Magnification control is established so that a unit increment of the zoom controller, such as a cursor on a tablet, results in a constant increase in the degree of magnification. The coefficients required for the interpolation are generated in real time avoiding the need for time consuming table look-ups.
U.S. Pat. No. 5,784,047 (Cahill, III, et al.) describes a display scaler device. The display scaler device includes a memory for sending data, a first variable length buffer for receiving the data from the memory. A first scaler scales the data in a first direction. A buffer controller controls the first buffer and a memory controller controls sending of the data from the memory to the first variable length buffer. A main display controller sends control signals to the first scaler, the buffer controller, and the memory controller. The display scaler may further include a second buffer for receiving the scaled data from the first scaler and a second scaler for scaling the scaled data in a second direction. The display scaler generates a first image on a first display window and a second image on a second display window. The method may send a first data corresponding to a portion of the first image then store the first data in a first storage. A second data corresponding to a portion of the second image is sent and stored in a second storage. Some of the first data vertically and horizontally is scaled and transmitted for display, and then some of the second data is scaled vertically and horizontally and transmitted for display.
U.S. Pat. No. 5,850,207 (Eglit) provides a display controller to up-scale a source video image for display on a display unit of a computer system. An encoder circuit stores in a local memory pixel data of previous scan lines required for interpolation in a compressed format using differential pulse code modulation (DPCM) scheme. As a part of the DPCM scheme, encoder generates a predicted value for each source video pixel data as a function of at least one prior pixel data value in the scan line. However, when a slope over load condition is encountered, the decoder circuit changes the predicted value for a subsequent pixel data value to a different value, which may enable the graphics controller circuit to avoid a slope overload condition as to subsequent pixel data values. A decoder circuit decompresses the pixel data into original format prior to sending to an interpolator. The interpolator receives a present scan line and the decompressed data of previous scan lines, and interpolates the received pixels to generate additional pixels required for up-scaling the source video image. When a slope overload condition is encountered, an override circuitry causes the interpolator to use for interpolation a pixel data value in the present scan line instead of the pixel data value causing the slope overload condition.
U.S. Pat. No. 5,889,529 (Jones, et al.) teaches a system and method for dynamically resizing graphic images of variable image complexity to generate display images at a constant frame rate for output to a display device. In one frame, an image resolution is determined and a graphic image is drawn to the determined image resolution. In the subsequent frame, the graphic image is magnified to a target resolution prior to being output to a display device. The synchronization of the drawing of the graphic image and its display is managed by a swap buffer signal. The graphic images and their corresponding image resolutions are double buffered. The multiple channels are independently dynamic resized such that multiple display devices can independently resize graphic images of variable complexity at a constant frame rate.
U.S. Pat. No. 6,014,125 (Herbert) describes a scaling apparatus for horizontally and vertically scaling scan line information stored in a video memory prior to providing the scan line information to a computer display. Horizontal scaling apparatus is provided in which a first clock signal is provided for graphics portions of scan lines and a second clock signal is provided for video portions of scan lines. The second clock signal is enabled in a manner such that the second clock signal exhibits a predetermined phase relationship with respect to the first clock signal from scan line to scan line. The frequency of the second clock signal is selected to determine the scaling of the video portion of the scan line. Vertical scaling apparatus is provided in which scan line information corresponding to first and second scan lines is retrieved from a video memory. A digital differential analyzer, external to the central processing unit, then determines respective weights for the first and second scan lines dependent on the amount of vertical scaling desired. The weights for the first and second scan lines are then provided to a weighted adder which adds the first and second scan lines according to these weights.
U.S. Pat. No. 6,594,404 (Smith) illustrates a method and apparatus for resizing a digital video image composed of a plurality of source pixels which are resized to a plurality of target pixels. The method employs a technique which expresses the point brightness energy associated with each source pixel as an area which spans two source pixel intervals, each the area span having a shape which is proportional to the energy distribution of the source pixel with time; creating for each target pixel a sample aperture of duration which is a function of the resizing factor, sampling the area spans with each sample aperture to provide, for each target pixel, a set of coefficients, each coefficient representing the proportion of an area span which is within the sample aperture; and scaling, with its associated coefficient, the amount of point brightness energy of each source pixel whose area span appears within any given sample aperture.
U.S. Pat. No. 6,577,778 (Wu, et al.) illustrates a method and apparatus that provides for interpolating a digital image in response to a requested degree of sharpness. An adjusting signal representing the requested degree of sharpness will then be generated. The interpolated pixel data are computed based on a 3 order or 4 order interpolation function for three sampling input pixels with an adjustable weight coefficient representing the selected degree of sharpness. The apparatus mainly includes: a control interface, a control unit, a vertical interpolation computation module, and a horizontal interpolation module. The vertical interpolation computation module and the horizontal interpolation module are implemented according to an interpolation function derived by the present invention. The control unit comprises a lookup table built according to a scaling function. The vertical scaling factor and the horizontal scaling factor required for the interpolation function can be obtained by looking up the lookup table according to the adjusting signal, and the position of the interpolated pixel. The degree of sharpness is controlled without having to implement an additional sharp control circuit.
U.S. Patent Application 2002/0154123A1 (Harasimiuk) illustrates a method and a system for scaling a digital source image consisting of a grid of X by Y pixels into a target image of a different resolution. The method includes mapping the source pixels onto the target pixels. The method further includes scaling the source image in the X or Y direction to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter. The contributions for each intermediate pixel are accumulated. Each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and subsequently scaling the intermediate pixels in the other direction by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel. Each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels.
U.S. Patent Application 2003/0085912A1 (Soo, et al.) describes a system and method for image scaling interpolation. Input image pixel amplitude data is received at an input pixel resolution and image pixel amplitude data in one or two dimensions is output at a higher pixel resolution. User-programmable coefficients are selectable according to the nature and quality of the input image data such that sharpness of the output image data can be at least partially tailored to the image.
U.S. Patent Application 2003/0174148A1 (Chia, et al.) provides a method for scaling an image frame by an off-screen technology. An image frame consisting of n rows and m columns of data is stored into a storage device. The image frame is divided into a plurality of image portions. Then, the plurality of image portions are picked in sequence to a frame buffer register. An image scaling operation is performed for each picked image portion, and then the scaled image portion is cleared from the frame buffer register.
U.S. Patent Application 2003/0198399A1 (Atkins) describes a method for image scaling for image scaling that begins by selecting an input pixel from a first image. An input edge characteristic is determined from an input window associated with the input pixel. The input edge characteristic is determined from a plurality of predetermined edge characteristics that are associated with sets of filter coefficient vectors. An output window is generated by filtering the input window with a corresponding set of filter coefficients associated with the input edge characteristic. An output image is generated by repeating the above for a plurality of input pixels associated with the first image.
U.S. Patent Application 2004/0179030A1 (Cole, et al.) teaches a method for displaying an image having a first aspect ratio with a display device having a second aspect ratio. The method includes receiving image data for the image, buffering the image data and creating a frame of the image at the first aspect ratio, defining a first sub-frame and a second sub-frame for the frame of the image at the second aspect ratio, including spatially offsetting the second sub-frame from the first sub-frame in one direction, and alternating between displaying the first sub-frame in a first position and the second sub-frame in a second position spatially offset from the first position with the display device, including optically scaling a displayed image of the first sub-frame and a displayed image of the second sub-frame in the one direction.